﻿//
// KwCombinatorics v2.0.x
// Copyright © 2009-2012 - Kasey Osborn (Kasewick@gmail.com)
// Ms-PL - Use and redistribute freely
//
// File: Permutation.cs
//

using System;
using System.Collections.Generic;
using System.Text;

namespace Kw.Combinatorics
{
    /// <summary>
    /// Represents an arrangement of all values from a supplied range.
    /// </summary>
    /// <remarks>
    /// <para>
    /// Use the <see cref="Width"/> property to get the number of elements in an
    /// arrangement. This is sometimes called the "order" of a permutation.
    /// 
    /// Use the <see cref="Rank"/> property to choose a row from an ordered table of
    /// permutations.
    /// 
    /// Use the <see cref="GetEnumerator">default enumerator</see> to enumerate over
    /// all the elements of the permutation.
    /// 
    /// Use <see cref="GetRows">GetRows</see> to enumerate over an ordered table of all
    /// possible permutations.
    /// 
    /// Use <see cref="GetRowsForAllWidths">GetRowsForAllWidths</see> to enumerate over
    /// every table of all widths from (1..<see cref="Width"/>).
    /// 
    /// Use the <see cref="P:Kw.Combinatorics.Permutation.Item(System.Int32)">indexer</see>
    /// to get an element of the sequence.
    /// 
    /// Use the <see cref="Permute">Permute</see>
    /// method to rearrange a supplied array based on the current sequence.
    /// </para>
    /// <para>
    /// The default appearance of a <see cref="Permutation"/> is a list of integers
    /// (starting at 0) enclosed in braces. The appearance may be tailored 3 ways:
    /// <ul>
    ///   <li>
    ///     Map each element to a different value using the
    ///     <see cref="GetEnumerator">default enumerator</see> or the
    ///     <see cref="P:Kw.Combinatorics.Permutation.Item(System.Int32)">indexer</see>.
    ///   </li>
    ///   <li>
    ///     Use <see cref="Permute">Permute</see> and output the rearranged values.
    ///   </li>
    ///   <li>
    ///     Declare and use a subclass of <see cref="Permutation"/> and override
    ///     <see cref="System.Object.ToString">ToString</see>.
    ///     (See <see cref="GetRowsForAllWidths">GetRowsForAllWidths</see> for an example.)
    ///   </li>
    /// </ul>
    /// </para>
    /// <para>
    /// For more information, see:
    /// </para>
    /// <para>
    /// <em>http://en.wikipedia.org/wiki/Permutation</em>
    /// </para>
    /// </remarks>
    /// <example>
    /// <para>
    ///  Iterating over all widths of <c>Permutation (3)</c> produces:
    /// </para>
    /// <para>
    ///    { 0 }<br />
    ///    { 0, 1 } { 1, 0 }<br />
    ///    { 0, 1, 2 } { 0, 2, 1 } { 1, 0, 2 } { 1, 2, 0 } { 2, 0, 1 } { 2, 1, 0 }
    /// </para>
    /// </example>
    public class Permutation :
        ICloneable,
        IComparable,
        System.Collections.IEnumerable,
        IComparable<Permutation>,
        IEquatable<Permutation>,
        IEnumerable<int>
    {
        private int[] data;   // The arrangement of the current rank.
        private long rank;    // Row index of the ordered table of permutations.

        internal static readonly long[] factorial = new long[]
        {
            1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 
            479001600, 6227020800, 87178291200, 1307674368000, 20922789888000,
            355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000
        };

        #region Constructors

        /// <summary>
        /// Make an empty <see cref="Permutation"/>.
        /// </summary>
        public Permutation ()
        {
            this.data = new int[0];
            this.rank = 0;
        }


        /// <summary>
        /// Make a copy of a <see cref="Permutation"/>.
        /// </summary>
        /// <param name="source">Instance to copy.</param>
        /// <exception cref="ArgumentNullException">When <em>source</em> is <b>null</b>.</exception>
        public Permutation (Permutation source)
        {
            if (source == null)
                throw new ArgumentNullException ("source");

            this.data = new int[source.data.Length];
            source.data.CopyTo (this.data, 0);

            this.rank = source.rank;
        }


        /// <summary>Make a new <see cref="Permutation"/> of the supplied <em>width</em>.</summary>
        /// <param name="width">Number of elements of new sequence.</param>
        /// <example>
        /// <code source="Examples\PermutationExample01\PermutationExample01.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentOutOfRangeException">
        /// When <em>width</em> is less than 0 or greater than 20.
        /// </exception>
        public Permutation (int width)
        {
            if (width < 0)
                throw new ArgumentOutOfRangeException ("width", "Value is less than zero.");

            if (width > MaxWidth)
                throw new ArgumentOutOfRangeException ("width", "Value is greater than maximum allowed.");

            this.data = new int[width];
            for (int i = 0; i < width; ++i)
                this.data[i] = i;

            this.rank = 0;
        }


        /// <summary>
        /// Make a new <see cref="Permutation"/> of the supplied <em>width</em> and <em>rank</em>.
        /// </summary>
        /// <param name="width">Number of elements of new sequence.</param>
        /// <param name="rank">Initial row index of the ordered <see cref="Permutation"/> table.</param>
        /// <example>
        /// <code source="Examples\PermutationExample01\PermutationExample01.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentOutOfRangeException">
        /// When <em>width</em> less than 0 or greater than 20.
        /// </exception>
        public Permutation (int width, long rank)
        {
            if (width < 0)
                throw new ArgumentOutOfRangeException ("width", "Value is less than zero.");

            if (width > MaxWidth)
                throw new ArgumentOutOfRangeException ("width", "Value is greater than maximum allowed.");

            this.data = new int[width];
            Rank = rank;
        }


        /// <summary>
        /// Make a new <see cref="Permutation"/> from the supplied elements.
        /// </summary>
        /// <param name="source">Array of integers.</param>
        /// <example>
        /// <code source="Examples\PermutationExample03\PermutationExample03.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentNullException">When <em>source</em> is <b>null</b>.</exception>
        /// <exception cref="ArgumentOutOfRangeException">
        /// When length of <em>source</em> is greater than 20 or contains invalid data.
        /// </exception>
        /// <exception cref="ArgumentOutOfRangeException">
        /// When <em>source</em> contains out of range values.
        /// </exception>
        /// <exception cref="ArgumentException">
        /// When <em>source</em> contains repeated values.
        /// </exception>
        public Permutation (int[] source)
        {
            if (source == null)
                throw new ArgumentNullException ("source");

            if (source.Length > MaxWidth)
                throw new ArgumentOutOfRangeException ("source", "Too many values.");

            this.data = new int[source.Length];
            source.CopyTo (this.data, 0);

            //
            // Perform validation & ranking:
            //

            this.rank = 0;
            bool[] isUsed = new bool[Width];

            for (int i = 0; i < Width; ++i)
            {
                if (this.data[i] < 0 || this.data[i] >= Width)
                    throw new ArgumentOutOfRangeException ("source", "Value is out of range.");

                if (isUsed[this.data[i]])
                    throw new ArgumentException ("Value is repeated.", "source");
                isUsed[this.data[i]] = true;

                int digit = 0;
                for (int j = 0; j < this.data[i]; ++j)
                    if (!isUsed[j])
                        ++digit;

                this.rank += digit * Factorial (Width - i - 1);
            }
        }

        #endregion

        #region Properties

        /// <summary
        /// >Number of elements in the <see cref="Permutation"/>.  Also known as 'order'.
        /// </summary>
        public int Width
        { get { return data.Length; } }


        /// <summary>
        /// Total count of distinct sequences in the <see cref="Permutation"/> table.
        /// </summary>
        public long Height
        {
            get { return data.Length == 0? 0 : Factorial (data.Length); }
        }


        /// <summary>
        /// Row index of the ordered <see cref="Permutation"/> table.
        /// </summary>
        /// <remarks>
        /// Any assigned value out of range will be normalized to (0..<see cref="Height"/>-1).
        /// </remarks>
        /// <example>
        /// <code source="Examples\PermutationExample03\PermutationExample03.cs" lang="cs" />
        /// </example>
        public long Rank
        {
            get
            {
                return rank;
            }
            set
            {
                // Normalize the new rank.
                long newRank = value % Factorial (data.Length);
                if (newRank < 0)
                    newRank += Factorial (data.Length);

                rank = newRank;

                //
                // Perform unranking:
                //

                bool[] isUsed = new bool[data.Length];
                int[] factoradic = new int[data.Length];

                // Compute the factoradic for the given rank.
                for (int i = data.Length - 1; i >= 0; --i)
                {
                    factoradic[i] = (int) (newRank / Factorial (i));
                    newRank -= factoradic[i] * Factorial (i);
                }

                // Build the permutation from the diminishing factoradic.
                for (int j = data.Length - 1; j >= 0; --j)
                    for (int newAtom = 0; ; ++newAtom)
                        if (!isUsed[newAtom])
                            if (factoradic[j] > 0)
                                --factoradic[j];
                            else
                            {
                                data[data.Length - j - 1] = newAtom;
                                isUsed[newAtom] = true;
                                break;
                            }
            }
        }


        /// <summary>
        /// Get an element of the <see cref="Permutation"/> at the supplied column.
        /// </summary>
        /// <param name="index">Index value.</param>
        /// <returns>Sequence value at <em>index</em>.</returns>
        /// <example>
        /// <code source="Examples\PermutationExample05\PermutationExample05.cs" lang="cs" />
        /// </example>
        /// <exception cref="IndexOutOfRangeException">
        /// When <em>index</em> not in range (0..<see cref="Width"/>-1).
        /// </exception>
        public int this[int index]
        { get { return data[index]; } }

        #endregion

        #region Member methods

        /// <summary>Make a copy of this <see cref="Permutation"/>.</summary>
        /// <remarks>Implements the deprecated <see cref="System.ICloneable"/> interface.</remarks>
        /// <returns>Copy of the object.</returns>
        /// <exclude />
        public object Clone ()
        { return new Permutation (this); }


        /// <summary>Compare two <see cref="Permutation"/>s.</summary>
        /// <param name="obj">Target of the comparison.</param>
        /// <returns>A signed integer indicating the sort order of this instance to <em>obj</em>.</returns>
        public int CompareTo (object obj)
        { return CompareTo (obj as Permutation); }


        /// <summary>Compare two <see cref="Permutation"/>s.</summary>
        /// <param name="other">Target of the comparison.</param>
        /// <returns>A signed integer indicating the sort order of this instance to <em>other</em>.</returns>
        public int CompareTo (Permutation other)
        {
            if ((object) other == null)
                return 1;

            int result = this.Width - other.Width;

            if (result == 0)
                if (this.Rank > other.Rank)
                    result = 1;
                else if (this.Rank < other.Rank)
                    result = -1;

            return result;
        }


        /// <summary>
        /// Indicate whether two <see cref="Permutation"/>s have the same value.
        /// </summary>
        /// <param name="obj">Target of the comparison.</param>
        /// <returns>
        /// <b>true</b> if <em>obj</em> has the same value as this object; otherwise, <b>false</b>.
        /// </returns>
        public override bool Equals (object obj)
        { return Equals (obj as Permutation); }


        /// <summary>
        /// Indicate whether two <see cref="Permutation"/>s have the same value.
        /// </summary>
        /// <param name="other">Target of the comparison.</param>
        /// <returns>
        /// <b>true</b> if <em>other</em> has the same value as this instance; otherwise, <b>false</b>.
        /// </returns>
        public bool Equals (Permutation other)
        {
            return (object) other != null && other.Rank == Rank && other.Width == Width;
        }


        /// <summary>Get an object-based enumerator of the elements.</summary>
        /// <returns>object-based elemental enumerator.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ()
        { return GetEnumerator (); }


        /// <summary>Enumerate over all elements of a <see cref="Permutation"/>.</summary>
        /// <returns>An <c>IEnumerator&lt;int&gt;</c> for this <see cref="Permutation"/>.</returns>
        /// <example>
        /// <code source="Examples\PermutationExample05\PermutationExample05.cs" lang="cs" />
        /// </example>
        public IEnumerator<int> GetEnumerator ()
        {
            for (int index = 0; index < Width; index++)
                yield return data[index];
        }


        /// <summary>Get the hash oode of the <see cref="Permutation"/>.</summary>
        /// <returns>A 32-bit signed integer hash code.</returns>
        public override int GetHashCode ()
        { return unchecked ((int) Rank); }


        /// <summary>
        /// Enumerate over all rows of all <see cref="Permutation"/>tables for every number
        /// of elements from (1..<see cref="Width"/>).
        /// </summary>
        /// <returns>An enumerator for a series of <see cref="Permutation"/> tables.</returns>
        /// <example>
        /// <code source="Examples\PermutationExample02\PermutationExample02.cs" lang="cs" />
        /// </example>
        /// <seealso cref="Permute"/>
        public IEnumerable<Permutation> GetRowsForAllWidths ()
        {
            for (int w = 1; w <= Width; ++w)
            {
                Permutation current = (Permutation) MemberwiseClone ();

                current.data = new int[w];
                for (int i = 0; i < current.data.Length; ++i)
                    current.data[i] = i;

                current.rank = 0;

                foreach (Permutation row in current.GetRows ())
                    yield return row;
            }
        }


        /// <summary>
        /// Enumerate over all rows of the <see cref="Permutation"/> table for every value of <see cref="Rank"/>.
        /// </summary>
        /// <remarks>
        /// If the start row is not at <see cref="Rank"/> 0, the enumeration will wrap around
        /// so that <see cref="Height"/> items are always produced.
        /// </remarks>
        /// <returns>An enumerator for a <see cref="Permutation"/> table.</returns>
        /// <example>
        /// <code source="Examples\PermutationExample01\PermutationExample01.cs" lang="cs" />
        /// </example>
        public IEnumerable<Permutation> GetRows ()
        {
            if (Height > 0)
            {
                long startRank = Rank;

                for (Permutation current = (Permutation) MemberwiseClone (); ; )
                {
                    yield return current;

                    current.Rank = current.Rank + 1;
                    if (current.Rank == startRank)
                        break;
                }
            }
        }


        /// <summary>
        /// Provide a readable form of the <see cref="Permutation"/> sequence.
        /// </summary>
        /// <remarks>Result is enclosed in braces and separated by commas.</remarks>
        /// <returns>A <b>string</b> that represents the sequence.</returns>
        /// <example>
        /// <code source="Examples\PermutationExample03\PermutationExample03.cs" lang="cs" />
        /// </example>
        public override string ToString ()
        {
            if (Height == 0)
                return ("{ }");

            StringBuilder result = new StringBuilder ("{ ");

            for (int i = 0; ; )
            {
                result.Append (this[i]);

                ++i;
                if (i >= Width)
                    break;

                result.Append (", ");
            }

            result.Append (" }");

            return result.ToString ();
        }

        #endregion

        #region Static methods

        /// <summary>
        /// Apply a <see cref="Permutation"/> sequence to rearrange the supplied list or array.
        /// </summary>
        /// <typeparam name="T">Type of items to rearrange.</typeparam>
        /// <param name="arrangement">New arrangement for items.</param>
        /// <param name="source">list of items to rearrange.</param>
        /// <returns>Rearranged objects.</returns>
        /// <example>
        /// <code source="Examples\PermutationExample04\PermutationExample04.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentNullException">When <em>arrangement</em> or <em>source</em> is <b>null</b>.</exception>
        /// <exception cref="ArgumentOutOfRangeException">When length of
        /// <em>source</em> is less than <see cref="Width"/>.</exception>
        public static List<T> Permute<T> (Permutation arrangement, IList<T> source)
        {
            if (arrangement == null)
                throw new ArgumentNullException ("arrangement");

            if (source == null)
                throw new ArgumentNullException ("source");

            if (source.Count < arrangement.Width)
                throw new ArgumentException ("Not enough supplied values.", "source");

            List<T> result = new List<T> (arrangement.Width);

            for (int i = 0; i < arrangement.Width; ++i)
                result.Add (source[arrangement.data[i]]);

            return result;
        }


        /// <summary>Indicate whether two <see cref="Permutation"/>s are equal.</summary>
        /// <param name="param1">A <see cref="Permutation"/>.</param>
        /// <param name="param2">A <see cref="Permutation"/>.</param>
        /// <returns><b>true</b> if supplied <see cref="Permutation"/>s are equal;
        /// otherwise, <b>false</b>.</returns>
        public static bool operator == (Permutation param1, Permutation param2)
        {
            if ((object) param1 == null)
                return (object) param2 == null;
            else
                return param1.Equals (param2);
        }


        /// <summary>Indicate whether two <see cref="Permutation"/>s are not equal.</summary>
        /// <param name="param1">A <see cref="Permutation"/>.</param>
        /// <param name="param2">A <see cref="Permutation"/>.</param>
        /// <returns><b>true</b> if supplied sequences are not equal;
        /// otherwise, <b>false</b>.</returns>
        public static bool operator != (Permutation param1, Permutation param2)
        { return !(param1 == param2); }


        /// <summary>Indicate whether the left <see cref="Permutation"/> is less than
        /// the right <see cref="Permutation"/>.</summary>
        /// <param name="param1">A <see cref="Permutation"/>.</param>
        /// <param name="param2">A <see cref="Permutation"/>.</param>
        /// <returns><b>true</b> if the left sequence is less than
        /// the right sequence otherwise, <b>false</b>.</returns>
        public static bool operator < (Permutation param1, Permutation param2)
        {
            if ((object) param1 == null)
                return (object) param2 != null;
            else
                return param1.CompareTo (param2) < 0;
        }


        /// <summary>Indicate whether the left <see cref="Permutation"/> is greater than or equal to
        /// the right <see cref="Permutation"/>.</summary>
        /// <param name="param1">A <see cref="Permutation"/>.</param>
        /// <param name="param2">A <see cref="Permutation"/>.</param>
        /// <returns><b>true</b> if the left sequence is greater than or equal to
        /// the right sequence otherwise, <b>false</b>.</returns>
        public static bool operator >= (Permutation param1, Permutation param2)
        { return !(param1 < param2); }


        /// <summary>Indicate whether the left <see cref="Permutation"/> is greater than
        /// the right <see cref="Permutation"/>.</summary>
        /// <param name="param1">A <see cref="Permutation"/>.</param>
        /// <param name="param2">A <see cref="Permutation"/>.</param>
        /// <returns><b>true</b> if the left sequence is greater than
        /// the right sequence otherwise, <b>false</b>.</returns>
        public static bool operator > (Permutation param1, Permutation param2)
        {
            if ((object) param1 == null)
                return false;
            else
                return param1.CompareTo (param2) > 0;
        }

        /// <summary>Indicate whether the left permutation is less than or equal to
        /// the right permutation.</summary>
        /// <param name="param1">A <see cref="Permutation"/>.</param>
        /// <param name="param2">A <see cref="Permutation"/>.</param>
        /// <returns><b>true</b> if the left sequence is less than or equal to
        /// the right sequence otherwise, <b>false</b>.</returns>
        public static bool operator <= (Permutation param1, Permutation param2)
        { return !(param1 > param2); }


        /// <summary>Calculate factorial of the supplied value.</summary>
        /// <param name="n">non-negative integer</param>
        /// <returns><em>n</em>!</returns>
        /// <exception cref="IndexOutOfRangeException">
        /// When <em>n</em> is less than 0 or greater than 20.
        /// </exception>
        /// <exclude />
        static public long Factorial (int n)
        { return factorial[n]; }


        /// <summary>
        /// Get the maximum number of elements that may be in any <see cref="Permutation"/>.
        /// </summary>
        /// <returns>
        /// The maximum number of elements that may be in any <see cref="Permutation"/>
        /// due to Int64 computational limitations.
        /// </returns>
        static public int MaxWidth
        { get { return factorial.Length - 1; } }


        /// <summary>
        /// Increment the rank of the supplied <see cref="Permutation"/> by 1.
        /// The increment operator can appear before or after its operand.
        /// </summary>
        /// <param name="param">A <see cref="Permutation"/> to modify.</param>
        /// <returns>The supplied <see cref="Permutation"/> with the next higher rank.</returns>
        /// <example>
        /// <code source="Examples\PermutationExample03\PermutationExample03.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentNullException">When <em>param</em> is <b>null</b>.</exception>
        public static Permutation operator ++ (Permutation param)
        {
            if (param == null)
                throw new ArgumentNullException ("param");

            param.Rank = param.Rank + 1;
            return param;
        }


        /// <summary>
        /// Decrement the rank of the supplied <see cref="Permutation"/> by 1.
        /// The decrement operator can appear before or after its operand.
        /// </summary>
        /// <param name="param">A <see cref="Permutation"/> to modify.</param>
        /// <returns>The supplied <see cref="Permutation"/> with the previous lower rank.</returns>
        /// <exception cref="ArgumentNullException">When <em>param</em> is <b>null</b>.</exception>
        public static Permutation operator -- (Permutation param)
        {
            if (param == null)
                throw new ArgumentNullException ("param");

            param.Rank = param.Rank - 1;
            return param;
        }

        #endregion
    }
}
